#include "String.h"


// 求next[]数组

// next数组的优化 nextval[]

void next_val(int &nextval[], int next[])
{
    nextval[1] = 0;
    for(int j=2; j<T.length; j++)
    {
        if(T.ch[next[j]] == T.ch[j])  // 字符重合
        {
            nextval[j] = nextval[next[j]];
        }
        else
        {
            nextval[j] = next[j];
        }
    }
}

int Index_KMP(SString S, SString T, int next[])
{
    int i=1, j=1;
    while(i <= S.length && j <= T.length)
    {
        if(j==0 || S.ch[i]==T.ch[j])
        {
            ++i;
            ++j;    // 继续比较后继字符
        }
        else
        {
            j = next[j];
        }
    }

    if(j > T.length)
    {
        return i-T.length;
    }
    else
    {
        return 0;
    }
    
}